﻿#pragma once
#include<assert.h>
// 原因是pair需要包含用到的头文件
//底层是二叉搜索树，结点里面存储的是pair
//调整结点的时候，只有当修改到了某个结点的孩子结点的时候，才会修改该结点的平衡因子
template<class K, class V>
struct AVLTreeNode {
	pair<K, V> _kv;
	AVLTreeNode<K, V>* _left = nullptr;
	AVLTreeNode<K, V>* _right = nullptr;
	// 需要parent指针，后续更新平衡因子可以看到
	AVLTreeNode<K, V>* _parent = nullptr;
	int _bf = 0;//balance factor平衡因子

	AVLTreeNode(const pair<K, V>& kv)
		:_kv(kv)
	{}//自己走初始化列表即可
};

template<class K, class V>
class AVLTree {
public:
	typedef AVLTreeNode<K, V> Node;//只有接口可以设置成公有,这里设置成公有是为了测试代码
public:
	void Inorder()
	{
		_Inorder(_root);
		cout << endl;
	}
	int Size()
	{
		return _Size(_root);
	}
	Node* Find(const K& key)//查找结点
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}
	int Height()
	{
		return _Height(_root);
	}
	bool IsBalanceTree()
	{
		return _IsBalanceTree(_root);
	}
	bool Insert(const pair<K, V>& kv)//思路其实跟二叉搜索树那里是差不多的
	{
		if (_root == nullptr)
		{
			Node* cur = new Node(kv);
			_root = cur;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else {
				return false;
			}
		}
		//找到合适的位置，此时需要链接结点
		cur = new Node(kv);
		//if (parent->_left == cur)
		//{
		//	parent->_left = cur;
		//}
		//else {
		//	parent->_right = cur;
		//}//感觉这样写也是可以的,感觉也是行得通的
		if (kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		else {
			parent->_right = cur;
		}
		cur->_parent = parent;
		//更新平衡因子
		while (parent)//使用parent来判断，因为根结点的parent的结果是空
		{
			if (cur == parent->_left)
			{
				--parent->_bf;
			}
			else if (cur == parent->_right)
			{
				++parent->_bf;
			}

			if (parent->_bf == 0)
			{//如果此时_bf为0，停止向上更新
				break;
			}
			else if (parent->_bf == -1 || parent->_bf == 1)
			{//此时需要继续向上比较更新
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)//到这里我的parent和cur一定都是已经换了位置的，
			{//不平衡，此时需要来旋转
				if (parent->_bf == -2 && cur->_bf == -1)//左边高，右单旋
				{//纯粹左边高
					RotateR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == 1)//右边高，左单旋
				{//纯粹右边高
					RotateL(parent);
				}
				//一下这两种方法都有一种简记的方法，直接将subLR或subRL作为根结点，parent和subL/subR作为左右子树，靠哪边就作为哪边的树
				else if (parent->_bf == -2 && cur->_bf == 1)
				{//左边高的右边高,因为最后是右边高，我先调用左旋，将右边高的转移到左边去，随后再来调用右旋，左旋之后的树是符合右旋的
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{//右边高的左边高，因为最后是左边高，我先调用右旋，将左边高的转移到右边去，随后再来调用左旋，右旋之后的树是符合左旋的
					RotateRL(parent);
				}
				break;//旋转了之后我就直接退出循环即可
			}
			else {
				assert(false);//走到这里来的话，就报错
			}
		}
	}
private:
	void _Inorder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_Inorder(root->_left);
		cout << root->_kv.first << " ";//里面的成员变量是pair
		_Inorder(root->_right);
	}
	int _Size(Node* root)//类似于求二叉树结点的个数
	{
		return root == nullptr ? 0 : 1 + _Size(root->_left) + _Size(root->_right);
	}
	int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}
	bool _IsBalanceTree(Node* root)//检测这个二叉树是不是AVL树
	{
		// 空树也是AVL树
		if (nullptr == root) return true;
		// 计算pRoot结点的平衡因⼦：即pRoot左右⼦树的⾼度差
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		int diff = rightHeight - leftHeight;
		// 如果计算出的平衡因⼦与pRoot的平衡因⼦不相等，或者// pRoot平衡因⼦的绝对值超过1，则⼀定不是AVL树
		if (abs(diff) >= 2)
		{
			cout << root->_kv.first << "⾼度差异常" << endl;
			return false;
		}
		if (root->_bf != diff)
		{
			cout << root->_kv.first << "平衡因⼦异常" << endl;
			return false;
		}
		// pRoot的左和右如果都是AVL树，则该树⼀定是AVL树
		return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
	}
	void RotateR(Node* parent)
	{//需要改变三个结点，但是改变结点就需要改变parent指针
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)//防止subLR此时为空的情况所以这个时候需要来判断，防止对空结点的解引用
			subLR->_parent = parent;
		Node* ppnode = parent->_parent;//因为我下面的parent的_parent已经被修改了，但是我有需要来链接新的根节点，所以此时我需要先记录一下
		subL->_right = parent;
		parent->_parent = subL;

		if (parent == _root)//为什么是这样判断呢？因为一开始我改变的一直都是parent结点中的成员变量，没有改变parent的指向，即没有出现parent=谁谁谁
		{
			_root = subL;//subL作为新的根
			subL->_parent = nullptr;
		}
		else {
			if (ppnode->_left == parent)
			{
				ppnode->_left = subL;//链接新的子树
				subL->_parent = ppnode;//修改新的子树_parent的指向
			}
			else {
				ppnode->_right = subL;//链接新的子树
				subL->_parent = ppnode;//修改新的子树_parent的指向
			}
		}
		//更新平衡因子
		parent->_bf = subL->_bf = 0;
	}
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
		Node* ppnode = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;
		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else {
			if (ppnode->_left == parent)
			{
				ppnode->_left = subR;
				subR->_parent = ppnode;
			}
			else {
				ppnode->_right = subR;
				subR->_parent = ppnode;
			}
		}
		//更新平衡因子
		parent->_bf = subR->_bf = 0;
	}
	//其实双旋不难，都是单旋的叠加，只是顺序不同，修改的主要是三个结点的平衡因子,三种情况是要看subLR和subRL的平衡因子情况来决定的
	//因为在单旋中都处理了ppnode与parent的链接问题，在双旋中就不用处理了
	void RotateLR(Node* parent)//此时是左子树高，左子树的右子树高，因为LR，L在前
	{//思路:先对subL进行左旋，再对parent进行右旋
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;

		RotateL(parent->_left);
		RotateR(parent);
		//int bf = subLR->_bf;//现在都已经修改了，还写在这里干嘛？
		//修改平衡因子
		if (bf == -1)//此时在subLR的左子树插入
		{
			subL->_bf = 0;
			parent->_bf = 1;
			subLR->_bf = 0;
		}
		else if (bf == 1)//此时在subLR的右子树插入
		{
			subL->_bf = -1;
			parent->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == 0)//此时新插入的结点就是subLR，此时全部都为0
		{
			subL->_bf = 0;
			parent->_bf = 0;
			subLR->_bf = 0;
		}
		else {
			assert(false);
		}
	}
	void RotateRL(Node* parent)//此时是右子树高，右子树的左子树高，因为RL,R在前
	{//思路:先对subR进行右旋，再对parent进行左旋
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;

		RotateR(subR);
		RotateL(parent);
		//int bf = subLR->_bf;//现在都已经修改了，还写在这里干嘛？
		if (bf == -1)//此时在subLR的左子树插入
		{
			subR->_bf = 1;
			parent->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == 1)//此时在subLR的右子树插入
		{
			subR->_bf = 0;
			parent->_bf = -1;
			subRL->_bf = 0;
		}
		else if (bf == 0)//此时新插入的结点就是subLR，此时全部都为0
		{
			subR->_bf = 0;
			parent->_bf = 0;
			subRL->_bf = 0;
		}
		else {
			assert(false);
		}
	}
private:
	Node* _root = nullptr;
};